package com.kevinkk.tree;

import java.util.*;

/**
 * 迭代法 后序 遍历二叉树
 */

public class BinaryTreePostorderTraversal {
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> st = new LinkedList<>();
            if(root != null) st.addFirst(root);

            while(!st.isEmpty()){
                TreeNode temp = st.peekFirst();
                if(temp == null){
                    st.removeFirst();
                    res.add(st.removeFirst().val);
                }else{
                    st.addFirst(null);
                    if(temp.right != null) st.addFirst(temp.right);
                    if(temp.left != null) st.addFirst(temp.left);
                }
            }
            return res;
        }
    }
}
